package code.class3;


public class TestDemo {
    public static void main(String[] args) {
        int[] arr = {-3, 2, 1, 8, 5, 4, 2, 3, 5, 13};
        int ans = firstMissingPositive(arr);
        System.out.println("ans = " + ans);
    }

    private static int firstMissingPositive(int[] arr) {
        int l = 0, r = arr.length;
        while (l < r) {
            if (arr[l] == l+1) {
                l++;
            } else if (arr[l] <= l || arr[l] > r || arr[arr[l] - 1] == arr[l]) {
                swap(arr, l, --r);
            } else {
                swap(arr, l, arr[l]-1);
            }
        }
        return l+1;
    }

    public static void swap(int[] arr, int x, int y) {
        int t = arr[x];
        arr[x] = arr[y];
        arr[y] = t;
    }

}
